/*
 * InterviewAlgorithm.cpp
 *
 *  Created on: 2013-1-14
 *      Author: EthanHuang
 */
#include <iostream>
#include <memory>
#include "InterviewAlgorithm.h"
using namespace std;

void InterviewAlgorithm::printMatrixInCycles(int** arr, int rows, int cols)
{
	cout<<"The matrix cycle is: "<<endl;
	for(int start = 0; start < rows / 2 && start < cols / 2; ++ start)
	{
		_printMatrixCylcleLine(arr, rows, cols, start);
	}
}


void InterviewAlgorithm::_printMatrixCylcleLine(int** arr, int rows, int cols,
		int start)
{
	int endX = rows - 1 - start;
	int endY = cols - 1 - start;

	//print the top line in the cycle
	for(int j = start; j <= endY; ++j)
	{
		cout<<arr[start][j]<<" ";
	}

	//print the right column in the cycle
	if(endX > start)
	{
		for(int i = start + 1; i <= endX; ++i)
		{
			cout<<arr[i][endY]<<" ";
		}
	}

	//print the bottom row in the cycle
	if(endY > start)
	{
		for(int j = endY - 1; j >= start; --j)
		{
			cout<<arr[endX][j]<<" ";
		}
	}

	//print the left column in the cycle
	if(endX > start +1)
	{
		for(int i = endX -1; i >= start + 1; --i)
		{
			cout<<arr[i][start]<<" ";
		}
	}

}

void InterviewAlgorithm::mergeSort(int* a, int* temp, int left, int right) {
	if(right > left){
		int middle = (right + left)/2;
		mergeSort(a, temp, left, middle);
		mergeSort(a, temp, middle + 1, right);
		mergeSortMerge(a, temp, left, middle + 1, right);
	}
}

void InterviewAlgorithm::mergeSortDriver(int* a, int size) {
	if(size <= 1)
	{
		return;
	}
	else
	{
		int *temp = new int[size];
		//call the mergeSort function
		mergeSort(a, temp, 0, size - 1);
		delete[] temp;
	}
}

void InterviewAlgorithm::mergeSortMerge(int* a, int* temp, int leftPos, int rightPos,
		int rightEnd) {
	int tempP = 0;
	int left = leftPos;
	int leftEnd = rightPos -1;
	int right = rightPos;
	//Copy elements in left array or right array into temp increasingly and copy back to a
	while(left <= leftEnd && right <= rightEnd)
	{
		temp[tempP] = (a[left] < a[right]) ? a[left] : a[right];
		++tempP;
		a[left] < a[right] ? ++left : ++right;
	}
	if(right > rightEnd)
	{
		for(; left <= leftEnd; ++left, ++tempP)
		{
			temp[tempP] = a[left];
		}
	}
	if(left > leftEnd)
	{
		for(; right <= rightEnd; ++right, ++tempP)
		{
			temp[tempP] = a[right];
		}
	}
	//Copy back form tempP to a[left] to a[rightEnd]
	left = leftPos;
	tempP = 0;
	while(left <= rightEnd)
	{
		a[left] = temp[tempP];
		++left;
		++tempP;
	}
}
